2024 暑期牛客多校训练营 10

📅Date: 2024-09-02 📚Category: 算法竞赛 📂Tag: 牛客 📑Word: 14.3k

2024 暑期牛客多校训练营 10

A Surrender to My Will

签到题

B std::pair

模拟，建立二叉树即可

D Is it rated?

题目大意

有 \(n\) 场\(\textbf{按顺序}\)的比赛，第 \(i\) 场比赛有表现分 \(p_i\)。参加第 \(i\) 场比赛后你的分数 \(r\) 将变为 \(r\times(1-k)+k\times p_i\)。你可以选择最多 \(m\) 场比赛不参加。给定初始分数 \(r_0\) 和参数 \(k\)。问经过至少 \(n-m\) 场比赛后，分数最高是多少。

题解做法

根据数据范围 \(k\geq0.1\), 经过至多 200 场后之前的分数影响将在精度误差之内, 故只需要考虑最后 \(\min(m+200,n)\) 场比赛即可.

场上某大佬做法（可忽略 k 范围）

const int N = 1e6 + 5;
ll a[N];
db k, p[N];
#define vt vct<db>
vt dfs (int l, int r)
{
    if (l == r) rty {0, k * a[l]};
    int m = l + r >> 1;
    vt L = dfs (l, m);
    vt R = dfs (m + 1, r);
    int i = 0, j = 0;
    vt ans = {0};
    while (i + 1 < L.sz && j + 1 < R.sz)
    {
        if (L[i] * p[j + 1] + R[j + 1] > L[i + 1] * p[j] + R[j])
            j++, ans.pb (L[i] * p[j] + R[j]);
        else
            i++, ans.pb (L[i] * p[j] + R[j]);
    }
    while (i + 1 < L.sz ) i++, ans.pb (L[i] * p[j] + R[j]);
    while (j + 1 < R.sz ) j++, ans.pb (L[i] * p[j] + R[j]);
    rty ans;
}
void solve()
{
    cin >> n >> m >> k >> x;
    p[0] = 1;
    fo (i, 1, n) p[i] = p[i - 1] * (1 - k), cin >> a[i];
    vt rp = dfs (1, n);
    db ans = 0;
    fo (i, n - m, n)
    {
        ans = max (ans, x * p[i] + rp[i]);
//      print (x * p[i] + rp[i])
    }
    sp (12);
    ANS;
    rty;
}

用类似归并排序的方式来求区间内选择 \(1\sim len\) 场的最大得分. O(\(n\log n\))

分析: 在相同场次下, 不同的选取方式大小关系与初始分数无关. 基于原始 dp \(f_{i,j}\) 表示前 \(i\) 场, 选了 \(j\) 场参加的最大得分. 寻找性质快速合并.

下面来证明正确性：

F Collinear Exception

按顺序模拟，可以加入时暴力标记新增直线覆盖的点，经分析复杂度正确 O(能过)

#include<bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define fi first
#define se second
#define ls (rt<<1)
#define rs (rt<<1|1)
#define Ls (tr[rt].lc)
#define Rs (tr[rt].rc)

const int N=1e3+10;
int n,vis[N][N];
vector<pii>ans;
char s[N*N];
void add(int x1,int y1,int x2,int y2)
{
    int dltx=(x1-x2),dlty=(y1-y2),gd=__gcd(abs(dltx),abs(dlty));
    dltx/=gd;
    dlty/=gd;
    int nx=x1,ny=y1;
    while(nx>=1&&nx<=n&&ny>=1&&ny<=n)
    {
        vis[nx][ny]=1;
        nx+=dltx;
        ny+=dlty;
    }
    nx=x1,ny=y1;
    while(nx>=1&&nx<=n&&ny>=1&&ny<=n)
    {
        vis[nx][ny]=1;
        nx-=dltx;
        ny-=dlty;
    }
    return;
}
int main()
{
    read(n);
    for(int i=1,x,y;i<=n*n;i++)
    {
        read(x),read(y);
        if(!vis[x][y])
        {
            s[i]='1';
            vis[x][y]=1;
            for(auto p:ans)
                add(p.fi,p.se,x,y);
            ans.push_back(make_pair(x,y));
        }
        else s[i]='0';
    }
    puts(s+1);
    flushout();
    return 0;
}

H All-in at the Pre-flop

诈骗题 答案为 \(\dfrac{a}{a+b}\)

J Doremy's Starch Trees

换根 dp，维护子树内部点是否满足要求，换根时当前根的新子树 dfs 序是新根 dfs 序的补集。用 dfs 重新编号对每个点的边排序然后二分可以 O(\(\log n\)) 判断是否存在合法边。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int T,n,dfn[N],Time,last[N],f[N],eto[N];
vector<int>e[N],e2[N];

void dfs(int now,int fa)
{
    dfn[now]=++Time;
    for(int to:e[now])
        if(to!=fa)dfs(to,now);
    last[now]=Time;
    return;
}
bool find(int x,int l,int r)
{
    if(l>r)return 0;
    if(e2[x].back()<l)return 0;
    if(e2[x][0]>r)return 0;
    int pos=0;
    int L=0,rr=e2[x].size()-1,mid;
    while(L<=rr)
    {
        mid=(L+rr)>>1;
        if(e2[x][mid]>=l)pos=mid,rr=mid-1;
        else L=mid+1;
    }
    return e2[x][pos]<=r;
}
void dfs2(int now,int fa)
{
    f[now]=1;
    for(int to:e[now])
        if(to!=fa)
        {
            dfs2(to,now);
            f[now]&=f[to];
            eto[to]=find(now,dfn[to],last[to]);
            f[now]&=eto[to];
        }
    return;
}
int ans=-1;
void dfs3(int now,int fa)
{
//  printf("%d %d %d\n",now,fa,f[now]);
    if(f[now])
    {
        ans=now;
        return;
    }
    vector<int>g;
    g.clear();
    g.resize(e[now].size());
    int l=e[now].size();
    for(int i=0;i<l;i++)
        if(e[now][i]!=fa)g[i]=f[e[now][i]]&eto[e[now][i]];
        else g[i]=1;
    for(int i=l-2;i>=0;i--)
        g[i]&=g[i+1];
    int fg=1;
    for(int i=0;i<l;i++)
    {
        int to=e[now][i];
        if(to!=fa)
        {
            if(fg&&(i<l-1?g[i+1]:1)&&(find(to,1,dfn[to]-1)||find(to,last[to]+1,n)))
                dfs3(to,now);
            fg&=eto[to]&f[to];
        }
    }
}
int main()
{
    cin>>T;
    while(T--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)e2[i].clear(),e[i].clear();
        for(int i=2,p;i<=n;i++)
        {
            cin>>p;
            e2[p].push_back(i);
            e2[i].push_back(p);
        }
        for(int i=2,p;i<=n;i++)
        {
            cin>>p;
            e[p].push_back(i);
            e[i].push_back(p);
        }
        Time=0;
        dfs(1,0);
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<e2[i].size();j++)e2[i][j]=dfn[e2[i][j]];
            sort(e2[i].begin(),e2[i].end());
        }   
        dfs2(1,0);
        ans=-1;
        dfs3(1,0);
        cout<<ans<<'\n';
    }
    flushout();
    return 0;
}
/*
1
4
1 2 3
1 1 1
*/

K Doremy's IQ 2

显然是先往小走再往大走（或者反过来），枚举最小走到哪，最大的端点单调不增可以用双指针维护。O(n)

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int T,n,a[N],ans;
int work()
{
    int l=1,r=n,res=0;
    for(int l=n;l;l--)
        if(l>(-a[l])&&a[l]<=0)
        {
            while(a[r]>0&&n-r<a[r]-a[l])r--;
            res=max(res,r-l+1);
        }
    return res;
}
int main()
{
    read(T);
    while(T--)
    {
        read(n);
        for(int i=1;i<=n;i++)read(a[i]);
        ans=work();
        for(int i=1;i<=n;i++)a[i]=-a[i];
        reverse(a+1,a+n+1);
        ans=max(ans,work());
        write(ans-1);
    }
    flushout();
    return 0;
}

L Tada!

考虑枚举密码，将状态 \(A\) 变为 \(B\) 所需的步数等于 \(A-B\) (每一位在模 \(10\) 意义下分别做减法) 通过区间加减 \(1\)，变为 \(00000\) 的步数。
不难发现操作可逆，所以 \(A-B\) 变为 \(00000\) 的最少步数等于 \(00000\) 变为 \(A-B\) 的步数，所以从 \(00000\) 出发 \(\text{bfs}\) 求出每个 \(A-B\) 的最少步数即可，记作 \(f_{A-B}\)
当 \(n>1,t_i>1\) 时，只要 \(f_{A-B}\le t_i\) 一定可以成功，与奇偶性无关。
当 \(n=1\) 或 \(t_i=1\) 时，则需考虑奇偶性。
O(\(m10^n\))

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int T,n,m,cnt[N],d[6],D[6],num[6],f[N];
void init()
{
    memset(f,-1,sizeof(f));
    f[0]=0;
    queue<int>q;
    q.push(0);
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        for(int j=5,nw=now;j;j--)
            num[j]=nw%10,nw/=10;
        for(int i=1;i<=5;i++)
            for(int j=i,v;j<=5;j++)
                {
                    for(int k=i;k<=j;k++)
                        num[k]++,num[k]%=10;
                    v=0;
                    for(int k=1;k<=5;k++)
                        v=v*10+num[k];
                    if(f[v]==-1)
                    {
                        f[v]=f[now]+1;
                        q.push(v);
                    }
                    for(int k=i;k<=j;k++)
                        num[k]+=18,num[k]%=10;
                    v=0;
                    for(int k=1;k<=5;k++)
                        v=v*10+num[k];
                    if(f[v]==-1)
                    {
                        f[v]=f[now]+1;
                        q.push(v);
                    }

                    for(int k=i;k<=j;k++)
                        num[k]++,num[k]%=10;
                }
    }
    return;
}
int main()
{
    init();
    read(T);
    while(T--)
    {
        read(n),read(m);
        int mx=1;
        for(int i=1;i<=n;i++)mx*=10;
        for(int i=0;i<mx;i++)cnt[i]=0;
        for(int i=1,s,t;i<=m;i++)
        {
            read(s),read(t);
            int ns=s;
            for(int j=n;j;j--)
                num[j]=ns%10,ns/=10;
            for(int j=1;j<=n;j++)d[j]=num[j];
            for(int as=0,now,v;as<mx;as++)
            {
                now=as;
                for(int j=n;j;j--)
                    num[j]=now%10,now/=10;
                for(int j=1;j<=n;j++)
                    D[j]=num[j]-d[j],D[j]=(D[j]%10+10)%10;
                v=0;
                for(int j=1;j<=n;j++)v=v*10+D[j];
                if(f[v]==0&&t==1)continue;
                if(n==1&&(abs(t-f[v])&1))continue;
                if(f[v]<=t)cnt[as]++;
            }
        }
        int ans=0,pos=0;
        for(int i=0;i<mx;i++)
            if(cnt[i]==m)ans++,pos=i;
        if(ans>1)puts("MANY");
        else if(ans==1)
        {
            for(int j=1;j<=n;j++)num[j]=pos%10,pos/=10;
            for(int j=n;j;j--)
                putchar(num[j]+'0');
            putchar('\n');
        }
        else puts("IMPOSSIBLE");
    }
    flushout();
    return 0;
}
/*
1
3 3
003 1
003 3
025 1
*/

评论